#include <stdio.h>
#include <stdlib.h>
#define Maxsize 50

typedef struct BTNode
{
    int data;
    BTNode *lchild;
    BTNode *rchild;
} BTNode, *BTtree;

typedef struct SqQueue
{
    BTNode *data[Maxsize];
    int front;
    int rear;
} SqQueue;

// 队满条件 (q.rear+1) % MaxSize == q.front
// 队空条件 q.rear == q.front
// 队列中的元素个数 (q.rear - q.front + MaxSize) % MaxSize

// 初始化
void Init(SqQueue &q)
{
    q.front = 0;
    q.rear = q.front;
}

//入队
bool enQueue(SqQueue &q, BTNode *e)
{
    if ((q.rear + 1) % Maxsize == q.front)
        return false;
    q.data[q.rear] = e;
    q.rear = (q.rear + 1) % Maxsize;
    return true;
}

// 出队
bool deQueue(SqQueue &q, BTNode *&e)
{
    if (q.front == q.rear)
        return false;
    e = q.data[q.front];
    q.front = (q.front + 1) % Maxsize;
    return true;
}

// 输出
void print(SqQueue q)
{
    printf("front->");
    for (int i = q.front; i != q.rear; i = (i + 1) % Maxsize)
        printf("%d->", q.data[i]->data);
    printf("rear\n");
}

void LevelOrder(BTtree &T)
{
    SqQueue q;
    BTNode *node;
    Init(q);
    enQueue(q, T);
    while (q.front != q.rear)
    {
        deQueue(q, node);
        printf("%d\n", node->data);
        if (node->lchild)
            enQueue(q, node->lchild);
        if (node->rchild)
            enQueue(q, node->rchild);
    }
}

void LevelOrder1(BTtree &tree)
{
    if (!tree)
        return;
    BTNode *queue[Maxsize];
    int front = 0;
    int rear = 0;
    BTNode *p = NULL;
    // 根节点入队
    queue[rear] = tree;
    rear = (rear + 1) % Maxsize;
    // 循环遍历queue
    while (rear != front)
    {
        // 出队
        p = queue[front];
        front = (front + 1) % Maxsize;

        // visit
        printf("%d ", p->data);

        // 左右孩子入队
        if (p->lchild)
        {
            queue[rear] = p->lchild;
            rear = (rear + 1) % Maxsize;
        }

        if (p->rchild)
        {
            queue[rear] = p->rchild;
            rear = (rear + 1) % Maxsize;
        }
    }
}

void LevelOrder2(BTtree &tree)
{
    if (!tree)
        return;
    BTNode *queue[Maxsize];
    int front = 0;
    int rear = 0;
    BTNode *p = NULL;
    // 根节点入队
    queue[rear] = tree;
    rear = (rear + 1) % Maxsize;
    // 循环遍历queue
    while (rear != front)
    {
        // 获取当前层大小
        int size = (rear - front + Maxsize) % Maxsize; // 当前队列的大小
        while (size != 0)
        {
            // 出队
            p = queue[front];
            front = (front + 1) % Maxsize;

            // visit
            printf("%d ", p->data);

            // 左右孩子入队
            if (p->lchild)
            {
                queue[rear] = p->lchild;
                rear = (rear + 1) % Maxsize;
            }

            if (p->rchild)
            {
                queue[rear] = p->rchild;
                rear = (rear + 1) % Maxsize;
            }
            size--;
        }
        printf("\n");
    }
}

void LevelOrder3(BTtree &tree)
{
    if (!tree)
        return;
    BTNode *queue[Maxsize];
    int front = 0;
    int rear = 0;
    BTNode *p = NULL;
    // 根节点入队
    queue[rear] = tree;
    rear = (rear + 1) % Maxsize;
    int curSize = 1;
    int nextSize = 0;
    // 循环遍历queue
    while (rear != front)
    {

        // 出队
        p = queue[front];
        front = (front + 1) % Maxsize;
        curSize--;

        // visit
        printf("%d ", p->data);

        // 左右孩子入队
        if (p->lchild)
        {
            queue[rear] = p->lchild;
            rear = (rear + 1) % Maxsize;
            nextSize++;
        }

        if (p->rchild)
        {
            queue[rear] = p->rchild;
            rear = (rear + 1) % Maxsize;
            nextSize++;
        }

        if (curSize == 0)
        {
            // 当前层遍历完成
            printf("\n");
            curSize = nextSize;
            nextSize = 0;
        }
    }
}

// 测试
void InitTree(BTtree &T)
{
    T = (BTNode *)malloc(sizeof(BTNode));
    T->data = 0;
    BTNode *node;
    node = (BTNode *)malloc(sizeof(BTNode));
    node->data = 1;
    T->lchild = node;

    node = (BTNode *)malloc(sizeof(BTNode));
    node->data = 2;
    T->rchild = node;

    node = (BTNode *)malloc(sizeof(BTNode));
    node->data = 3;
    T->lchild->lchild = node;

    node = (BTNode *)malloc(sizeof(BTNode));
    node->data = 4;
    T->lchild->rchild = node;

    node = (BTNode *)malloc(sizeof(BTNode));
    node->data = 5;
    T->rchild->lchild = node;

    node = (BTNode *)malloc(sizeof(BTNode));
    node->data = 6;
    T->rchild->rchild = node;
}

int main(int argc, char const *argv[])
{
    // 队列测试
    // SqQueue q;
    // Init(q);
    // enQueue(q,1);
    // enQueue(q,2);
    // enQueue(q,3);
    // enQueue(q,4);
    // print(q);
    // int temp;
    // deQueue(q,temp);

    // 二叉树层序遍历测试
    BTtree T;
    InitTree(T);
    LevelOrder1(T);
    printf("\n\n");
    LevelOrder2(T);
    printf("\n");
    LevelOrder3(T);
    printf("\n");

    return 0;
}
